algo-aha

有负数数组，意味着presum[]无序，先想到presum解法，可配合其他条件

有负数数组、和>=T的最短子段

• https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/

用了presum[]和单调栈

int shortestSubarray(vector<int>& A, int T) {
	// 求presum[i]-presum[j]>=T的最短子段长
	// 对于左端点presum[j]，如果在presum[]中能找到下一个更小（或相等）的数presum[k]，
	// 因为presum[i]-presum[k]更大（或相等）、且子段i-k更短，所以presum[k]占优。
	// 只需考虑占优选项，用单调栈
	// 配合两指针法
	const int N = A.size();
	vector<long> presum(N + 1, 0);
	for (int i = 1; i <= N; i++) {
		presum[i] = presum[i - 1] + A[i - 1];
	}

	int ans = INT_MAX;
	deque<int> dq;
	for (int k = 0; k <= N; k++) {
		while (!dq.empty() && presum[k] <= presum[dq.back()]) {  // 只考虑占优策略
			dq.pop_back();
		}
		dq.push_back(k);

		while (!dq.empty() && presum[k] - presum[dq[0]] >= T) {
			ans = min(ans, k - dq[0]);
			dq.pop_front();  // dp[0]对后面的k都不会取得更短子段
		}
	}
	return ans != INT_MAX ? ans : -1;
}

用runningSum解法，至少O(NlgN)，超时

// Time Limit Exceeded
int shortestSubarray(vector<int>& A, int K) {
    map<int, int> mp; // sum=>lastIdx
    int runningSum = 0;
    mp[runningSum] = -1;

    int ans = INT_MAX;
    for (int i = 0; i < A.size(); i++) {
        runningSum += A[i];
        // 在旧runningSum集合mp中找toFind，
        // 使runningSum-toFind>=K，toFind<=runningSum-K
        int x = runningSum - K;
        auto ub = mp.upper_bound(x);
        for (auto it = mp.begin(); it != ub; it++) {
            ans = min(ans, i - it->second);
        }
        mp[runningSum] = i;
    }
    return ans != INT_MAX ? ans : -1;
}